When a problem has been shown to be NP-complete, often one has to be content with either exponential-time algorithms or resort to approximation algorithms that sacrifice the optimality of the solution, or with ad hoc ...